{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 隐语义模型的梯度下降求解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.算法实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "\"\"\"\n",
    "@输入参数：\n",
    "R：M*N 的评分矩阵\n",
    "P：初始化用户特征矩阵M*K\n",
    "Q：初始化物品特征矩阵N*K\n",
    "K：隐特征向量个数\n",
    "steps: 最大迭代次数\n",
    "alpha：步长\n",
    "lamda：正则化系数\n",
    "\n",
    "@输出：\n",
    "分解之后的 P，Q\n",
    "\"\"\"\n",
    "\n",
    "def LFM_grad_desc(R, K=2, steps=3000, alpha=0.0002, lamda=0.004):\n",
    "    M = len(R)         # R的行数M\n",
    "    N = len(R[0])      # R的列数N\n",
    "    P = np.random.rand(M,K) # 产生一个M * K的随机矩阵\n",
    "    Q = np.random.rand(N,K) # 产生一个N * K的随机矩阵\n",
    "    Q = Q.T # Q做转置\n",
    "    \n",
    "    for step in range(steps):\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                # 如果评分大于0，表示有评分，才考虑误差\n",
    "                if R[i][j] > 0:\n",
    "                    eij = R[i][j] - np.dot(P[i,:],Q[:,j]) # np.dot是点乘的意思, P[i,:]: 1 * K; Q[:,j]: K * 1\n",
    "                    for k in range(0, K):\n",
    "                        P[i][k] = P[i][k] + alpha * (2 * eij * Q[k][j] - 2 * lamda * P[i][k])\n",
    "                        Q[k][j] = Q[k][j] + alpha * (2 * eij * P[i][k] - 2 * lamda * Q[k][j])\n",
    "\n",
    "        # 根据更新之后的P、Q计算预测评分矩阵\n",
    "        # P和Q进行点乘\n",
    "        eR = np.dot(P,Q)\n",
    "        # 计算当前损失函数\n",
    "        e = 0\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                if R[i][j] > 0:\n",
    "                    e += (R[i][j]-np.dot(P[i,:],Q[:,j]))**2\n",
    "                    for k in range(K):\n",
    "                        e += lamda * (P[i][k]**2 + Q[k][j]**2) \n",
    "        \n",
    "        if e < 0.001:\n",
    "            break\n",
    "    return P, Q.T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "输入\n",
    "\n",
    "$$\n",
    "R: M \\times N \\\\\n",
    "P: M \\times K \\\\\n",
    "Q: K \\times N\n",
    "$$\n",
    "\n",
    "损失函数：\n",
    "\n",
    "$$\n",
    "L = \\sum (R - PQ)^2 + \\lambda {\\vert\\vert P \\vert\\vert}^2 + \\lambda {\\vert\\vert Q \\vert\\vert}^2\n",
    "$$\n",
    "\n",
    "当然这里的R是评分矩阵的**已有评分**\n",
    "\n",
    "也就是说\n",
    "\n",
    "$$\n",
    "\\widehat{R}_{ij} = P_{i1}Q_{1j} + ... + P_{iK}Q_{Kj}  = \\sum P_{ik}Q_{kj}\n",
    "$$\n",
    "\n",
    "上面的公式$k$要循环$(1, K)$\n",
    "\n",
    "对P求偏导数\n",
    "\n",
    "$$\n",
    "\\frac {\\partial L}{\\partial P} = \\sum 2 \\times (R-PQ) \\times (-Q^T) + 2\\lambda\\vert\\vert P \\vert\\vert\n",
    "$$\n",
    "\n",
    "梯度下降迭代公式：\n",
    "\n",
    "$$\n",
    "P_{下一轮} = P_{当前轮} + \\alpha (2\\sum(R-PQ)Q^T-2\\lambda\\vert\\vert P \\vert\\vert)\n",
    "$$\n",
    "\n",
    "Q的求解同理\n",
    "\n",
    "这里有一个矩阵求导的技巧：\n",
    "\n",
    "$$\n",
    "\\frac {\\partial PQ}{\\partial P} = Q^T\n",
    "$$\n",
    "\n",
    "假设\n",
    "\n",
    "$$\n",
    "P = [P_1, ... ,P_K] \\\\\n",
    "Q = [Q_1, ... ,Q_K]^T \\\\\n",
    "PQ = P_1Q_1 + ... + P_KQ_K \\\\\n",
    "\\frac {\\partial PQ}{\\partial P} = [Q_1, ... , Q_K] = Q^T\n",
    "$$\n",
    "\n",
    "标量针对向量进行求导\n",
    "\n",
    "\n",
    "$$\n",
    "\\frac {\\partial x}{\\partial Y} = [\\frac {\\partial x}{\\partial y_1}, ..., \\frac {\\partial x}{\\partial y_K}]\n",
    "$$\n",
    "\n",
    "### ppt矩阵求导详细推导\n",
    "\n",
    "\n",
    "$$\n",
    "P_u^T = (p_1, ..., p_k)\n",
    "$$\n",
    "\n",
    "$$\n",
    "Q_i = \\left(\n",
    "  \\begin{array}{c}\n",
    "          q_{1} \\\\\n",
    "          \\vdots \\\\\n",
    "          q_{k}\n",
    " \\end{array}\n",
    " \\right)\n",
    "$$\n",
    "\n",
    "所以\n",
    "\n",
    "$$\n",
    "P_u^TQ_i = (p_1, ..., p_k)\\left(\n",
    "  \\begin{array}{c}\n",
    "          q_{1} \\\\\n",
    "          \\vdots \\\\\n",
    "          q_{k}\n",
    " \\end{array}\n",
    " \\right) = p_1q_1 + ... + p_kq_k\n",
    "$$\n",
    "\n",
    "所以对$Q_i$求偏导为：\n",
    "\n",
    "$$\n",
    "\\frac {\\partial P_u^TQ_i}{\\partial P_u} = \\frac {\\partial (p_1q_1 + ... + p_kq_k)}{\\partial \\left(\n",
    "  \\begin{array}{c}\n",
    "          p_{1} \\\\\n",
    "          \\vdots \\\\\n",
    "          p_{k}\n",
    " \\end{array}\n",
    " \\right)} = \\left(\n",
    "  \\begin{array}{c}\n",
    "          q_{1} \\\\\n",
    "          \\vdots \\\\\n",
    "          q_{k}\n",
    " \\end{array}\n",
    " \\right) = Q_i\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\sum_i Q_iQ_i^T = Q_1Q_1^T + ... + Q_NQ_N^T = (Q_1, ..., Q_N)\\left(\n",
    "  \\begin{array}{c}\n",
    "          Q_{1}^T \\\\\n",
    "          \\vdots \\\\\n",
    "          Q_{N}^T\n",
    " \\end{array}\n",
    " \\right) = (Q_1, ..., Q_N)(Q_1^T, ..., Q_N^T)^T\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "P_u = \\left(\n",
    "  \\begin{array}{c}\n",
    "          p_{1} \\\\\n",
    "          \\vdots \\\\\n",
    "          p_{k}\n",
    " \\end{array}\n",
    " \\right)\n",
    "$$\n",
    "\n",
    "所以\n",
    "\n",
    "$$\n",
    "\\left(\n",
    "  \\begin{array}{c}\n",
    "          p_{u1} \\\\\n",
    "          \\vdots \\\\\n",
    "          p_{uk}\n",
    " \\end{array}\n",
    " \\right)\n",
    ":=\n",
    "\\left(\n",
    "  \\begin{array}{c}\n",
    "          p_{u1} \\\\\n",
    "          \\vdots \\\\\n",
    "          p_{uk}\n",
    " \\end{array}\n",
    " \\right)\n",
    " -\n",
    "2 \\times e_{ij} \\times \\alpha \\times\n",
    "\\left(\n",
    "  \\begin{array}{c}\n",
    "          q_{1i} \\\\\n",
    "          \\vdots \\\\\n",
    "          q_{ki}\n",
    " \\end{array}\n",
    " \\right)\n",
    " -\n",
    " 2 \\times \\alpha \\times \\lambda\n",
    " \\left(\n",
    "  \\begin{array}{c}\n",
    "          p_{u1} \\\\\n",
    "          \\vdots \\\\\n",
    "          p_{uk}\n",
    " \\end{array}\n",
    " \\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. 测试"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[5, 1, 4, 2, 3],\n",
       "       [1, 0, 3, 3, 4],\n",
       "       [5, 2, 0, 2, 5],\n",
       "       [1, 2, 4, 3, 5]])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R = np.array([[5,1,4,2,3],\n",
    "              [1,0,3,3,4],\n",
    "              [5,2,0,2,5],\n",
    "              [1,2,4,3,5]])\n",
    "\n",
    "nP,nQ = LFM_grad_desc(R)\n",
    "R"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1.81934903, 0.95791858],\n",
       "       [0.64127237, 1.33964577],\n",
       "       [1.40524923, 1.84553705],\n",
       "       [0.09605722, 2.11453667]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1.99870812, 0.72355862],\n",
       "       [0.08831666, 0.951575  ],\n",
       "       [1.10031007, 1.86652159],\n",
       "       [0.74830888, 1.04585253],\n",
       "       [0.72814274, 2.23043893]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nQ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[4.32945793, 1.07221021, 3.78982379, 2.36327662, 3.4613247 ],\n",
       "       [2.25102854, 1.33140845, 3.2060762 , 1.88094173, 3.45493589],\n",
       "       [4.14403729, 1.88027384, 4.99094464, 2.98172008, 5.13957971],\n",
       "       [1.72198157, 2.02062368, 4.05252108, 2.283374  , 4.78628828]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nP.dot(nQ.T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
